package com.leetcode;

/*
    *********************************************
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
           佛祖保佑       永无BUG
 */

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author wry
 * @description: 滑动窗口最大值
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 * //输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * //输出：[3,3,5,5,6,7]
 * @date 6/18/25 PM8:45
 */
public class No239 {
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int[] result = maxSlidingWindow(nums, 3);
        System.out.println(Arrays.toString(result));
    }

    /**
     * 1、对头放窗口内最大的数
     * 2、移动窗口时, 如果对尾数小于当前数, 则删除尾数, 直到尾数大于当前数
     * 3、移动窗口时, 移出的下标数据等于对头, 则删除队头(因为如果后面的数有大于的, 这个数就没用了; 没有的话, 这个数就是最大的)
     * 4、如果当前下标大于等于k-1, 则将对头放入结果数组
     *
     * @param nums 输入的整数数组
     * @param k    滑动窗口的大小
     * @return 每个滑动窗口的最大值组成的数组
     */
    static public int[] maxSlidingWindow(int[] nums, int k) {
        // 双端队列，用于维护窗口内元素的单调递减序列（队首始终为当前窗口最大值）
        Deque<Integer> deque = new ArrayDeque<>();
        // 结果数组，长度为 nums.length - k + 1（滑动窗口的数量）
        int[] res = new int[nums.length - k + 1];

        // 遍历数组元素，i为当前窗口的右边界索引
        for (int i = 0; i < nums.length; i++) {
            // 计算当前窗口的左边界索引 j = 右边界i - 窗口大小k + 1
            int j = i - k + 1;

            // 当窗口左边界向右移动（j-1 >= 0表示窗口已开始滑动），若移出窗口的元素是当前队列最大值（队首），则将其从队首移除
            if (j - 1 >= 0 && !deque.isEmpty() && nums[j - 1] == deque.peekFirst()) {
                deque.removeFirst();
            }
            // 从队尾移除所有小于当前元素的元素，确保队列保持单调递减（这些元素不可能成为后续窗口的最大值）
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            // 当窗口左边界j >= 0时，窗口已完整形成，队首元素即为当前窗口最大值，存入结果数组
            // 将当前元素加入队尾（此时队列仍保持单调递减）
            deque.addLast(nums[i]);
            if (j >= 0) {
                res[j] = deque.peekFirst();
            }
        }
        return res;
    }
}
